from collections import deque
import numpy as np
import time
from functools import wraps

def fn_timer(function):
    @wraps(function)
    def function_timer(*args, **kwargs):
        t0 = time.time()
        result = function(*args, **kwargs)
        t1 = time.time()
        print("Total time running :" + str(t1 - t0)+"seconds" )
        return result
    return function_timer

def swap_param(L, i, j):
    L[i], L[j] = L[j], L[i]
    return L


def heap_adjust(L, start, end):
    temp = L[start]
    i = start
    j = 2 * i
    while j <= end:
        if (j < end) and (L[j] < L[j + 1]):
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

@fn_timer
def heap_sort(L):
    L_length = len(L) - 1

    first_sort_count = int(L_length / 2)
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, L_length)

    for i in range(L_length - 1):
        L = swap_param(L, 1, L_length - i)
        heap_adjust(L, 1, L_length - i - 1)

    return [L[i] for i in range(1, len(L))]




if __name__ == '__main__':
    L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70, 25])
    L = deque(np.random.randint(0, 100, 100000))

    L.appendleft(0)
    print(heap_sort(L))

# 当数据量为1W的时候，堆排序与希尔加Sedgewick序列差不多。当数据上10W+的时候，明显希尔有优势